Termination w.r.t. Q proof of /tmp/tmps9fS9

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

minus(0) → 0
+(x, 0) → x
+(0, y) → y
+(minus(1), 1) → 0
minus(minus(x)) → x
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)
+(minus(+(x, 1)), 1) → minus(x)

Q is empty.

↳ QTRS

  ↳ RRRPoloQTRSProof

Q restricted rewrite system:
The TRS R consists of the following rules:

minus(0) → 0
+(x, 0) → x
+(0, y) → y
+(minus(1), 1) → 0
minus(minus(x)) → x
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)
+(minus(+(x, 1)), 1) → minus(x)

Q is empty.

The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

minus(0) → 0
+(x, 0) → x
+(0, y) → y
+(minus(1), 1) → 0
minus(minus(x)) → x
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)
+(minus(+(x, 1)), 1) → minus(x)

Q is empty.
The following rules can be removed by the rule removal processor [15] because they are oriented strictly by a polynomial ordering:

minus(0) → 0
+(minus(1), 1) → 0
minus(minus(x)) → x

Used ordering:
Polynomial interpretation [25]:

POL(+(x₁, x₂)) = x₁ + 2·x₂
POL(0) = 0
POL(1) = 0
POL(minus(x₁)) = 1 + x₁

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(0, y) → y
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)
+(minus(+(x, 1)), 1) → minus(x)

Q is empty.

The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(0, y) → y
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)
+(minus(+(x, 1)), 1) → minus(x)

Q is empty.
The following rules can be removed by the rule removal processor [15] because they are oriented strictly by a polynomial ordering:

+(minus(+(x, 1)), 1) → minus(x)

Used ordering:
Polynomial interpretation [25]:

POL(+(x₁, x₂)) = x₁ + x₂
POL(0) = 0
POL(1) = 1
POL(minus(x₁)) = x₁

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(0, y) → y
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)

Q is empty.

The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, 0) → x
+(0, y) → y
+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)

Q is empty.
The following rules can be removed by the rule removal processor [15] because they are oriented strictly by a polynomial ordering:

+(x, 0) → x
+(0, y) → y

Used ordering:
Polynomial interpretation [25]:

POL(+(x₁, x₂)) = x₁ + x₂
POL(0) = 2
POL(minus(x₁)) = x₁

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)

Q is empty.

The following Q TRS is given: Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))
+(x, +(y, z)) → +(+(x, y), z)

Q is empty.
The following rules can be removed by the rule removal processor [15] because they are oriented strictly by a polynomial ordering:

+(x, +(y, z)) → +(+(x, y), z)

Used ordering:
Polynomial interpretation [25]:

POL(+(x₁, x₂)) = 1 + x₁ + 2·x₂
POL(minus(x₁)) = x₁

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

                ↳ QTRS

                  ↳ Overlay + Local Confluence

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))

Q is empty.

The TRS is overlay and locally confluent. By [19] we can switch to innermost.

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

                ↳ QTRS

                  ↳ Overlay + Local Confluence

                    ↳ QTRS

                      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))

The set Q consists of the following terms:

+(x0, minus(x1))

Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

+¹(x, minus(y)) → +¹(minus(x), y)

The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))

The set Q consists of the following terms:

+(x0, minus(x1))

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

                ↳ QTRS

                  ↳ Overlay + Local Confluence

                    ↳ QTRS

                      ↳ DependencyPairsProof

                        ↳ QDP

                          ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

+¹(x, minus(y)) → +¹(minus(x), y)

The TRS R consists of the following rules:

+(x, minus(y)) → minus(+(minus(x), y))

The set Q consists of the following terms:

+(x0, minus(x1))

We have to consider all minimal (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

                ↳ QTRS

                  ↳ Overlay + Local Confluence

                    ↳ QTRS

                      ↳ DependencyPairsProof

                        ↳ QDP

                          ↳ UsableRulesProof

                            ↳ QDP

                              ↳ QReductionProof

Q DP problem:
The TRS P consists of the following rules:

+¹(x, minus(y)) → +¹(minus(x), y)

R is empty.
The set Q consists of the following terms:

+(x0, minus(x1))

We have to consider all minimal (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

+(x0, minus(x1))

↳ QTRS

  ↳ RRRPoloQTRSProof

    ↳ QTRS

      ↳ RRRPoloQTRSProof

        ↳ QTRS

          ↳ RRRPoloQTRSProof

            ↳ QTRS

              ↳ RRRPoloQTRSProof

                ↳ QTRS

                  ↳ Overlay + Local Confluence

                    ↳ QTRS

                      ↳ DependencyPairsProof

                        ↳ QDP

                          ↳ UsableRulesProof

                            ↳ QDP

                              ↳ QReductionProof

                                ↳ QDP

                                  ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

+¹(x, minus(y)) → +¹(minus(x), y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

+¹(x, minus(y)) → +¹(minus(x), y)
The graph contains the following edges 2 > 2